/*
剑指 Offer II 005. 单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

 

示例 1:

输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
示例 2:

输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。
示例 3:

输入: words = ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。
 

提示：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
 

注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/
*/

#include <vector>
#include <string>
#include <unordered_map>
using std::vector;
using std::string;
using std::unordered_map;

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();

        //hash for every word ,use bit 
        unsigned int dict[n];
        for (int i = 0; i < n; ++i)
        {
            unsigned int bitWord = 0;
            //caculate words[i]'s bit level hash
            for(int j = 0; j < words[i].size(); ++j)
            {
                bitWord |= (0x1 << (words[i][j] - 'a'));
            }
            dict[i] = bitWord;
        }

        int maxP = 0;
        for (int i = 0; i < n ; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                // words[i],words[j] not share common letters
                if((dict[i] & dict[j]) == 0)
                {
                    int product = words[i].size() * words[j].size();
                    if(product > maxP)
                    {
                        maxP = product;
                    }
                }
            }
        }

        return maxP;
    }
};

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        unordered_map<int,int> wordBitLen;
        int stringBitMask = 0;
        for (int i = 0; i < n; ++i)
        {
            stringBitMask = 0;
            for (auto ch : words[i])
            {
                stringBitMask |= 1 << (ch - 'a');
            }
            if (!wordBitLen.count(stringBitMask) || wordBitLen[stringBitMask] < words[i].size())
            {
                wordBitLen[stringBitMask] = words[i].size();   
            }

        }

        int maxP = 0;

        for (auto mask1 : wordBitLen)
        {
            for (auto mask2 : wordBitLen)
            {
                if ((mask1.first & mask2.first) == 0)
                {
                    int prod = mask1.second * mask2.second;
                    if (prod > maxP)
                    {
                        maxP = prod;
                    }
                }
            }
        }

        return maxP;
    }
};